--region AstarManager1.lua
--Author : east
--Date   : 2016/05/11
--generate by [generate_ui_code.py] automatically

local AstarManager  = {}



local function getTwoGLen(indexX1, indexY1, indexX2, indexY2)
    local numX = math.abs(indexX1 - indexX2);
    local numY = math.abs(indexY1 - indexY2);
    local diff = math.abs(numX-numY);
    local tempMin = numX > numY and numY or numX;
    return (math.pow(2, 2)*tempMin + diff);
end

local function checkIsInList(list, block)
    for i, v in ipairs(list) do
        if v == block then
            return true;
        end
    end
    return false;
end


----data from 0 to max-1
function AstarManager:search(data, width, height, startPos, endPos)
    -- print("first:", data[startPos.y][startPos.x-1])
    -- print("first:", data[startPos.y-1][startPos.x])
    -- print("first:", data[startPos.y-1][startPos.x-1])
    -- print("first:", startPos.y, startPos.x+1, data[startPos.y][startPos.x+1])
    -- print("first:", data[startPos.y+1][startPos.x])
    -- print("first:", data[startPos.y+1][startPos.x+1])
    print("first1:", data[startPos.y][startPos.x])
    print("first2:", data[endPos.y][endPos.x])
        
    local isCouldPass = false;
    local findPath = {};

    if #data+1 <= 0 or #data[0]+1 <= 0 then
        return findPath
    end



    local maxW = #data[0]+1;
    local maxH = #data+1;
    local blocks = {};
    local tempIsPath = false;
    for row = 0, maxH-1 do
        if blocks[row] == nil then
            blocks[row] = {};
        end
        for col = 0,maxW-1 do
            tempIsPath = false;
            if data[row][col] == 0 then
                tempIsPath = true;
            end
            blocks[row][col] = {isPath = tempIsPath, G = 0, H = 0, indexX = col, indexY = row, parent = nil, getF = function(self) return (self.G+self.H) end};
            -- if row == 30 and col == 41 then
            --     print("fuck:", blocks[row][col].isPath);
            --     dump(blocks[row][col])
            --     print("test:", tempIsPath);
            -- end
        end
    end
    -- print("okokok")
    -- dump(blocks);


    local curIndexX = startPos.x;
    local curIndexY = startPos.y;
    local posIndexX = endPos.x;
    local posIndexY = endPos.y;
    local curBlock = blocks[curIndexY][curIndexX];
    print("hhe", posIndexY, posIndexX)
    -- dump(blocks);
    local posBlock = blocks[posIndexY][posIndexX];

    

    local totalPathCount = 0;
    for row = 0, maxH-1 do
        for col = 0, maxW-1 do
            local tempBlock = blocks[row][col];
            if(tempBlock.isPath == true) then
                local numX = math.abs(col-posIndexX);
                local numY = math.abs(row-posIndexY);
                tempBlock.H = numX + numY;
            
                tempBlock.G = getTwoGLen(col, row, curIndexX, curIndexY);
                tempBlock.parent = nil;
                totalPathCount = totalPathCount + 1;
            end
            

        end
    end


    local openList = {curBlock};
    local closeList = {};

    local isFindPosBlock = false;

    while true do
        local tempOpenLen = #openList;
        if 0 >= tempOpenLen then
            print("can not find path");
            dump(closeList);
            break;
        end

        local tempMinOpenBlock = nil;
        local tempIt1 = 1;

        for it1 = 1, tempOpenLen do
            local tempOpenBlock = openList[it1];
            if not tempMinOpenBlock then
                tempMinOpenBlock = tempOpenBlock;
                tempIt1 = 1;
            elseif tempMinOpenBlock:getF() > tempOpenBlock:getF() then
                tempMinOpenBlock = tempOpenBlock;
                tempIt1 = it1;
            end
        end
        -- print("tempMinOpenBlock=============", tempMinOpenBlock, tempIt1);
        closeList[#closeList+1] = tempMinOpenBlock;
        table.remove(openList, tempIt1);

        if tempMinOpenBlock == posBlock then
            isFindPosBlock = true;
            print("find the target");
            break;
        end


        ----------------------find the min F
        -- print("begin=======================")
        -- print(tempMinOpenBlock.indexX, tempMinOpenBlock.indexY);
        -- dump(blocks);

        local tempBlock1;
        if tempMinOpenBlock.indexX > 0 then
            tempBlock1 = blocks[tempMinOpenBlock.indexY][tempMinOpenBlock.indexX-1];
            if not checkIsInList(openList, tempBlock1) and not checkIsInList(closeList, tempBlock1) and tempBlock1.isPath then
                print("haha===============1")
                tempBlock1.parent = tempMinOpenBlock;
                openList[#openList + 1] = tempBlock1;
            end
        end

        if tempMinOpenBlock.indexX < maxW-1 then
            tempBlock1 = blocks[tempMinOpenBlock.indexY][tempMinOpenBlock.indexX+1];
            
            if not checkIsInList(openList, tempBlock1) and not checkIsInList(closeList, tempBlock1) and tempBlock1.isPath then
                print("haha===============2")
                tempBlock1.parent = tempMinOpenBlock;
                openList[#openList + 1] = tempBlock1;
            end
        end
        if tempMinOpenBlock.indexY > 0 then
            tempBlock1 = blocks[tempMinOpenBlock.indexY-1][tempMinOpenBlock.indexX];
            if not checkIsInList(openList, tempBlock1) and not checkIsInList(closeList, tempBlock1) and tempBlock1.isPath then
                print("haha===============3")
                tempBlock1.parent = tempMinOpenBlock;
                openList[#openList + 1] = tempBlock1;
            end
        end
        if tempMinOpenBlock.indexY < maxH-1 then
            tempBlock1 = blocks[tempMinOpenBlock.indexY+1][tempMinOpenBlock.indexX];
            if not checkIsInList(openList, tempBlock1) and not checkIsInList(closeList, tempBlock1) and tempBlock1.isPath then
                print("haha===============4")
                tempBlock1.parent = tempMinOpenBlock;
                openList[#openList + 1] = tempBlock1;
            end
        end

        if tempMinOpenBlock.indexX > 0 and tempMinOpenBlock.indexY > 0 and (isCouldPass or (blocks[tempMinOpenBlock.indexY][tempMinOpenBlock.indexX - 1].isPath and blocks[tempMinOpenBlock.indexY - 1][tempMinOpenBlock.indexX].isPath)) then
            tempBlock1 = blocks[tempMinOpenBlock.indexY-1][tempMinOpenBlock.indexX-1];
            if not checkIsInList(openList, tempBlock1) and not checkIsInList(closeList, tempBlock1) and tempBlock1.isPath then
                print("haha===============5")
                tempBlock1.parent = tempMinOpenBlock;
                openList[#openList + 1] = tempBlock1;
            end
        end
        if tempMinOpenBlock.indexX > 0 and tempMinOpenBlock.indexY < maxH-1 and (isCouldPass or (blocks[tempMinOpenBlock.indexY][tempMinOpenBlock.indexX - 1].isPath and blocks[tempMinOpenBlock.indexY + 1][tempMinOpenBlock.indexX].isPath)) then
            tempBlock1 = blocks[tempMinOpenBlock.indexY+1][tempMinOpenBlock.indexX-1];
            if not checkIsInList(openList, tempBlock1) and not checkIsInList(closeList, tempBlock1) and tempBlock1.isPath then
                print("haha===============6")
                tempBlock1.parent = tempMinOpenBlock;
                openList[#openList + 1] = tempBlock1;
            end
        end
        if tempMinOpenBlock.indexX < maxW-1 and tempMinOpenBlock.indexY < maxH-1 and (isCouldPass or (blocks[tempMinOpenBlock.indexY][tempMinOpenBlock.indexX + 1].isPath and blocks[tempMinOpenBlock.indexY + 1][tempMinOpenBlock.indexX].isPath)) then
            tempBlock1 = blocks[tempMinOpenBlock.indexY+1][tempMinOpenBlock.indexX+1];
            if not checkIsInList(openList, tempBlock1) and not checkIsInList(closeList, tempBlock1) and tempBlock1.isPath then
                print("haha===============7")
                tempBlock1.parent = tempMinOpenBlock;
                openList[#openList + 1] = tempBlock1;
            end
        end
        if tempMinOpenBlock.indexX < maxW-1 and tempMinOpenBlock.indexY > 0 and (isCouldPass or (blocks[tempMinOpenBlock.indexY][tempMinOpenBlock.indexX + 1].isPath and blocks[tempMinOpenBlock.indexY - 1][tempMinOpenBlock.indexX].isPath)) then
            tempBlock1 = blocks[tempMinOpenBlock.indexY-1][tempMinOpenBlock.indexX+1];
            if not checkIsInList(openList, tempBlock1) and not checkIsInList(closeList, tempBlock1) and tempBlock1.isPath then
                print("haha===============8")
                tempBlock1.parent = tempMinOpenBlock;
                openList[#openList + 1] = tempBlock1;
            end
        end

        print("openList:", #openList);
        print("closeList:", #closeList);


    end

    -- if 1 then return end

    if isFindPosBlock == false then
        return findPath;
    end


    local tempBlock = posBlock;
    print("tempBlock.indexX:%d  tempBlock.indexY:%d", tempBlock.indexX, tempBlock.indexY);
    local isHadPrintAll = false;
    while (true) do
        for it2 = 1, #closeList do
            local tempCloseBlock = closeList[it2];
            if tempBlock == tempCloseBlock then
                tempBlock = tempCloseBlock.parent;
                table.remove(closeList, it2);
                print("tempBlock.indexX:%d  tempBlock.indexY:%d", tempBlock.indexX, tempBlock.indexY);
                if tempBlock == curBlock then
                    isHadPrintAll = true;
                end
                break;
            end
            
        end
        if isHadPrintAll then
            break;
        end
    end



end


return AstarManager






